//题目:
// 给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。
// 可以 按任意顺序 返回答案。
#include<iostream>
#include<vector>

using namespace std;
//代码:
class Solution 
{
    vector<vector<int>> vv;
public:
    void dfs(const vector<int>& nums,vector<bool> arr,vector<int> v)
    {
        //dfs确定层数(深度)，而for循环决定每层选的具体值
        for(int i=0;i<nums.size();i++)
        {
            if(arr[i]==false)
            {
                v.push_back(nums[i]);
                arr[i]=true;

                if(v.size()==nums.size()){
                    vv.push_back(v);
                    return;
                }

                dfs(nums,arr,v);//进入下一层
                //回溯:本质原因是从dfs出来后，会继续从本层选值，但同层只能选一个值，故回溯，即扔掉“先前选的那个值”
                v.pop_back();//从dfs出来后，会从“同层”再选一个值，原先的arr[i]就要被去掉
                arr[i]=false;//恢复i状态，以免影响下一层的选址
            }    
        }
    }
    vector<vector<int>> permute(vector<int>& nums) 
    {
        vector<bool> arr(nums.size(),0);

        dfs(nums,arr,vector<int>());

        return vv;
    }
};